package algorithm.easy;

import java.util.Iterator;
import java.util.List;
import java.util.Stack;

public class Solution100 {

    public static boolean isSameTree(TreeNode p, TreeNode q) {
        boolean flag = false;
        if(p==null && q==null){         //双空 - 表示到底了，直接返回true
            flag = true;
            return flag;
        }else if(p==null || q==null){   //有一个为空
                flag = false;
                return  flag;
         }else{                         //两个都不为空
                if(p.val!=q.val){
                    flag = false;
                    return flag;
                }
        }

        TreeNode pleft = p.left;
        TreeNode qleft = q.left;
        if(pleft!=null && qleft!=null){
            flag = isSameTree(pleft,qleft);
        }else if(pleft!=null || qleft!=null){
            flag = false;
        }else{
            flag = true;
        }
        if(!flag){
            return flag;
        }

        TreeNode pright= p.right;
        TreeNode qright = q.right;
        if(pright!=null && qright!=null){
            flag = isSameTree(pright,qright);
        }else if(pright!=null || qright!=null){
            flag = false;
        }else{
            flag = true;
        }
        return flag;

    }

    public static boolean isSameTree2(TreeNode p, TreeNode q) {//双栈
        boolean flag = false;
        List<Integer> list1 = Solution94.inorderTraversal(p);
        List<Integer> list2 = Solution94.inorderTraversal(q);
        if(list1.size()!=list2.size()){
            return false;
        }else{
            Iterator<Integer> integers1 = list1.iterator();
            Iterator<Integer> integers2 = list2.iterator();
             while(integers1.hasNext() && integers2.hasNext()){
                 Integer value1 = integers1.next();
                 Integer value2 = integers2.next();
                 if(!value1.equals(value2)){
                     return false;
                 }
             }
             if(integers1.hasNext() || integers2.hasNext()){
                 flag = false;
             }else{
                 flag = true;
             }

        }
        return flag;
    }
    public static void main(String[] args){
        TreeNode p = TreeNode.init94();
        TreeNode q = TreeNode.init100();////TreeNode.init100();
        System.out.println(isSameTree2(p,q));
    }

}
